import collections
import sortedcontainers
class Solution(object):
    def matrixRankTransform(self, matrix):
        m = len(matrix)
        n = len(matrix[0])
        ans = [[0 for _ in range(n)] for _ in range(m)]
        d = collections.defaultdict(dict)
        du = collections.defaultdict(int)
        d_row_num = collections.defaultdict(dict)
        d_col_num = collections.defaultdict(dict)
        d_num = collections.defaultdict(dict)
        t = collections.defaultdict(set)
        root = {}
        for i in range(m):
            for j in range(n):
                if i in d_row_num[matrix[i][j]]:
                    d_row_num[matrix[i][j]][i].append(j)
                else:
                    d_row_num[matrix[i][j]][i] = [j]
                if j in d_col_num[matrix[i][j]]:
                    d_col_num[matrix[i][j]][j].append(i)
                else:
                    d_col_num[matrix[i][j]][j] = [i]
                d_num[matrix[i][j]][(i, j)] = (i, j)    

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]
        
        def union(x, y):
            rx = find(x)
            ry = find(y)
            if rx != ry:
                if rx > ry:
                    p[rx] = ry
                else:
                    p[ry] = rx

        for num, p in d_num.items():
            for i, j_list in d_row_num[num].items():
                if len(j_list) >= 2:
                    for j in range(1, len(j_list)):
                        union((i, j_list[0]), (i, j_list[j]))
            for j, i_list in d_col_num[num].items():
                if len(i_list) >= 2:
                    for i in range(1, len(i_list)):
                        union((i_list[0], j), (i_list[i], j))
            for key in p:
                t[find(key)].add(key)
                root[key]  = p[key]
        for i in range(m):
            st = sortedcontainers.SortedDict()
            for j in range(n):                
                if matrix[i][j] in st:
                    st[matrix[i][j]].add(j)
                else:
                    st[matrix[i][j]] = {j}
            for j in range(1, len(st)):
                for l_node in st.peekitem(j - 1)[1]:
                    for n_node in st.peekitem(j)[1]:
                        du[root[(i, n_node)]] += 1
                        d[root[(i, l_node)]][root[(i, n_node)]] = d[root[(i, l_node)]].get(root[(i, n_node)], 0) + 1

        for j in range(n):
            st = sortedcontainers.SortedDict()
            for i in range(m):
                if matrix[i][j] in st:
                    st[matrix[i][j]].add(i)
                else:
                    st[matrix[i][j]] = {i}
            for i in range(1, len(st)):
                for l_node in st.peekitem(i - 1)[1]:
                    for n_node in st.peekitem(i)[1]:
                        du[root[(n_node, j)]] += 1
                        d[root[(l_node, j)]][root[(n_node, j)]] = d[root[(l_node, j)]].get(root[(n_node, j)], 0) + 1

        now_set = set()
        for node in t:
            if du[node] == 0:
                now_set.add(node)
        index = 1
        while now_set:
            next_set = set()
            for node in now_set:
                for x, y in t[node]:
                    ans[x][y] = index
                for next_node in d[node]:
                    du[next_node] -= d[node][next_node]
                    if du[next_node] == 0:
                        next_set.add(next_node)
            index += 1
            now_set = next_set

        return ans               
            




data = Solution()
matrix = [[-37,-50,-3,44],[-37,46,13,-32],[47,-42,-3,-40],[-17,-22,-39,24]]
print(data.matrixRankTransform(matrix))